/**
 * 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
 * <p>
 * 珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一
 * 小时内不会再吃更多的香蕉。
 * <p>
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 * <p>
 * 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
 * <p>
 * <p>
 * <p>
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：piles = [3,6,7,11], h = 8
 * 输出：4
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：piles = [30,11,23,4,20], h = 5
 * 输出：30
 * <p>
 * <p>
 * 示例 3：
 * <p>
 * <p>
 * 输入：piles = [30,11,23,4,20], h = 6
 * 输出：23
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 1 <= piles.length <= 10⁴
 * piles.length <= h <= 10⁹
 * 1 <= piles[i] <= 10⁹
 * <p>
 * <p>
 * Related Topics 数组 二分查找 👍 447 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

public class ID00875KokoEatingBananas {
    public static void main(String[] args) {
        Solution solution = new ID00875KokoEatingBananas().new Solution();
    }


//leetcode submit region begin(Prohibit modification and deletion)


    class Solution {
        public int minEatingSpeed(int[] piles, int h) {
            int low = 1;
            int high = 0;
            //速度为线性递增，所以通过二分法来求速度
            //因为 piles.length <= h , 所以最大速度就为 数组中的最大值， 最小速度就是1（必须得吃）
            for (int pile : piles) {
                high = Math.max(high, pile);
            }
            int k = high;
            while (low < high) {//最后停在low = high
                int speed = (high - low) / 2 + low;
                //每个速度计算吃完时间
                long time = getTime(piles, speed);
                //吃完时间少，吃得有点快或者刚好
                if (time <= h) {
                    k = speed;
                    high = speed;
                } else if (time > h) { //吃完时间超时，说明要快点，要+1
                    low = speed + 1;
                }
            }
            return k;
        }

        public long getTime(int[] piles, int speed) {
            long time = 0;
            for (int pile : piles) {
                int curTime = (pile + speed - 1) / speed;//向上取整
                time += curTime;
            }
            return time;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)


}